Masala #1146

Shahar to’g’ri chiziqdan iborat, va bu shaharda mahalliy aholini yangiliklardan xabardor qilish uchun \(N\) ta Radio o’rnatilgan. Har bir radioning ovoz balandligi \(K\) ga teng. Radioda yangilik eshittirilganda \(A\)- koordinatada bo’lgan uyga \(B\)-koordinatada joylashtirilgan radioning ovozi \(max(K-|A-B|, 0)\) balandlikda eshitiladi. Sizga \(M\) ta uyning koordinatasi beriladi, har bir uy uchun ungacha yetib kelatidan eng baland radio ovozining balandligini aniqlang.

Kirish oqimining dastlabki satrida uchta butun son, \(N(1 \le N \le 250000)\), \(M(1 \le M \le 250000)\) va \(K(1 \le K \le 10^9)\) sonlari kiritiladi. Ikkinchi satrda \(N\) ta butun son, \(B_i(1 \le i \le N, 0 \le B_i \le 10^9)\) Radiolarning joylashgan koordinatalari kamaymaslik tartibida kiritiladi. Uchinchi satrda M ta butun son, \(A_i(1 \le i \le M, 0 \le A_i \le 10^9)\) uylarning joylashgan koordinatalari kiritiladi.

Chiqish oqimida har bir uy uchun alohida qatorda bittadan butun son, berilgan uyga radioning ovozi qanday balandlikda eshitilishini chop eting.